package com.mzy.linear_struct;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.function.Consumer;

/**
 * @Author: codermzy
 * @Date: 2024/04/09/12:50
 * @Description:
 */
public class MyBSTree {
    protected TreeNode root;

    protected class TreeNode {
        protected Integer value;
        protected TreeNode left;
        protected TreeNode right;

        protected TreeNode parent;


        public TreeNode(Integer value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }

        @Override
        public String toString() {
            return value.toString();
        }
    }


    public TreeNode insert(Integer value) {

        TreeNode newNode = this.createTreeNode(value);

        // 判断是否是第一次插入
        if (root == null) {
            root = newNode;
        } else {
            insertNode(root, newNode);
        }
        checkBalance(newNode);
        return newNode;
    }

    protected void checkBalance(TreeNode newNode) {

    }

    protected TreeNode createTreeNode(Integer value) {
        return new TreeNode(value);
    }

    public void preOrderTraverse(Consumer<Integer> consumer) {
        preOrderTraverseNode(root, consumer);
    }

    private void preOrderTraverseNode(TreeNode root, Consumer<Integer> consumer) {
        if (root == null) {
            return;
        }
        consumer.accept(root.value);
        preOrderTraverseNode(root.left, consumer);
        preOrderTraverseNode(root.right, consumer);
    }

    public void inOrderTraverse() {
        inOrderTraverseNode(root);
    }

    private void inOrderTraverseNode(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrderTraverseNode(root.left);
        System.out.println(root);
        inOrderTraverseNode(root.right);
    }


    public void postOrderTraverse() {
        postOrderTraverseNode(root);
    }

    private void postOrderTraverseNode(TreeNode root) {
        if (root == null) {
            return;
        }

        postOrderTraverseNode(root.left);
        postOrderTraverseNode(root.right);
        System.out.println(root);
    }


    private void insertNode(TreeNode root, TreeNode newNode) {


        if (root.value > newNode.value) {

            if (root.left == null) {
                root.left = newNode;
                newNode.parent = root;
            } else {
                insertNode(root.left, newNode);
            }
        } else if (root.value < newNode.value) {
            if (root.right == null) {
                root.right = newNode;
                newNode.parent = root;
            } else {
                insertNode(root.right, newNode);
            }
        }


    }


    /*public void levelOrderTraverse() {

        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.println(node);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }

    }*/

    public void levelOrderTraverse() {
        if (root == null) {
            return;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> ans = new ArrayList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            List<Integer> list = new ArrayList<>();
            while (n-- > 0) {
                TreeNode node = queue.poll();
                list.add(node.value);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ans.add(list);

        }
    }


    public int getMax() {
        TreeNode current = root;
        int max = 0;
        while (current != null && current.right != null) {
            TreeNode rightNode = current.right;
            max = rightNode.value;
            current = current.right;
        }
        return max;
    }

    public int getMin() {
        TreeNode current = root;
        int min = 0;
        while (current != null && current.left != null) {
            TreeNode leftNode = current.left;
            min = leftNode.value;
            current = current.left;
        }
        return min;
    }


    public boolean search(Integer value) {
        TreeNode node = searchNode(value);
        return node != null;
    }

    private TreeNode searchNode(Integer value) {
        TreeNode current = root;
        TreeNode parent = null;
        while (current != null) {
            if (value.equals(current.value)) return current;

            parent = current;
            if (value > current.value) current = current.right;
            if (value < current.value) current = current.left;

            current.parent = parent;
        }
        return null;
    }

    private boolean remove(Integer value) {

        TreeNode current = searchNode(value);
        if (current == null) {
            return false;
        }
        // 当前 current 是要删除的元素
        // 1. 如果是叶子节点直接进行删除
        if (current.left == null && current.right == null) {
            // 判断当前节点在左边还是右边
            if (isLeft(current, value)) {
                current.parent.left = null;
            } else if (isRight(current, value)) {
                current.parent.right = null;
            } else { // 根节点的情况
                root = null;
            }
        }
        // 2.1 如果不是叶子节点且只有左子节点
        else if (current.right == null) {
            // 判断是否是根节点
            if (current == root) {
                root = current.left;
            } else if (isLeft(current, value)) {
                current.parent.left = current.left;
            } else {
                current.parent.right = current.left;
            }
        }
        // 2.2 如果不是叶子节点且只有右子节点
        else if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (isRight(current, value)) {
                current.parent.right = current.right;
            } else {
                current.parent.left = current.right;
            }
        } else {      // 左右节点都有的情况
            // 前驱节点：比当前节点小一点点，但 是当前节点右子节点中最大的
            // 后继节点：比当前节点大一点点，但 是当前节点左子节点中最小的
            TreeNode successor = getSuccessor(current);
            // 判断是否是根节点
            if (current == root) {
                root = successor;
            } else if (isLeft(current, value)) { // 不是根节点
                current.parent.left = successor;
            } else if (isRight(current, value)) {
                current.parent.right = successor;
            }


        }
        return true;
    }

    private TreeNode getSuccessor(TreeNode delNode) {
        // 拿到右边的节点
        TreeNode current = delNode.right;
        TreeNode successor = null;
        // 获取右边最小的节点
        while (current != null) {
            successor = current;
            current = current.left;
            if (current != null) {
                current.parent = successor;
            }
        }
        System.out.println("删除节点：" + delNode.value + "   后继节点：" + successor);


        if (successor != delNode.right) {
            assert successor != null;
            successor.parent.left = successor.right;
            successor.right = delNode.right;
        }

        assert successor != null;
        successor.left = delNode.left;
        return successor;
    }

    private static boolean isLeft(TreeNode node, Integer value) {
        return value.equals(node.parent.left.value);
    }

    private static boolean isRight(TreeNode node, Integer value) {
        return value.equals(node.parent.right.value);
    }

    public static void main(String[] args) {
        // MyBSTree tree = new MyBSTree();
        // tree.insert(11);
        // tree.insert(7);
        // tree.insert(15);
        // tree.insert(5);
        // tree.insert(9);
        // tree.insert(3);
        // tree.insert(6);
        // tree.insert(8);
        // tree.insert(10);
        // tree.insert(13);
        // tree.insert(20);
        // tree.insert(12);
        // tree.insert(14);
        // tree.insert(18);
        // tree.insert(25);
        // tree.insert(19);
        // tree.preOrderTraverse(System.out::println);
        // // System.out.println(tree.getMax());
        // // System.out.println(tree.getMin());
        // tree.levelOrderTraverse();
        // // System.out.println(tree.remove(3));
        // // System.out.println(tree.remove(5));
        // System.out.println(tree.remove(11));
        // // System.out.println(tree.search(6));
        // // System.out.println(tree.search(41));
        // // System.out.println(tree.search(0));
        // tree.levelOrderTraverse();

    }


}
